#!/usr/bin/env python3
# -*-coding: utf-8-*-

import random
'''
Netherlansflag  荷兰国旗问题
给定一个数组arr，和一个数num，请把小于num的数放在数组的 左边，等于num的数放在数组的中间，大于num的数放在数组的右边
'''

def generate_random_array(max_size: int, max_value: int) -> list:
    length = random.randint(0, max_size)
    arr = []
    for i in range(length):
        arr.append(random.randint(0, max_value))
    return arr

def netherlands_flag(arr: list, pl: int, pr: int, num: int) -> list:
    if not arr or len(arr) < 2: return
    less = pl -1
    more = pr + 1
    while pl < more:
        if arr[pl] < num:
            less += 1
            arr[less], arr[pl] = arr[pl], arr[less]
            pl += 1
        elif arr[pl] == num:
            pl += 1
        else:
            more -= 1
            arr[pl], arr[more] = arr[more], arr[pl]
    return [less + 1, more - 1]


def main():
    sortedArrayMaxSize = 50
    maxValue = 100
    A = generate_random_array(sortedArrayMaxSize, maxValue)
    # B[0] <= B[1] 
    B =  netherlands_flag(A, 0, len(A)-1, 46)
    print(B)
    print(A)

main()